package Leetcode.动态规划;

import java.util.Arrays;

/**
 * 数字塔问题
 */
public class TowerOfNumbers {
    public static void main(String[] args) {
//        System.out.println("路径和：" + DataTower_dowToUp());
        System.out.println("路径和：" + DataTower_upToDown());
    }

    static int [][] arr ={
                        {8},
                        {12,15},
                        {3,9,6},
                        {8,10,5,12},
                        {16,4,18,10,9}};
    public static int n= arr.length;//数塔层数
    public static int[][] dp =new int[n][n];//最大和
    public static int[][] path =new int[n][n];//路径
    static int DataTower_upToDown() {
        // 初始化第一行的dp值
        dp[0][0] = arr[0][0];

        // 从第二行开始向上计算最大路径和
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                // 判断是否为当前行的第一个元素
                if (j == 0) {
                    dp[i][j] = arr[i][j] + dp[i - 1][j];

                }
                // 判断是否为当前行的最后一个元素
                else if (j == i) {
                    dp[i][j] = arr[i][j] + dp[i - 1][j - 1];

                }
                // 对于中间的元素，选择较大的子路径
                else if (dp[i - 1][j - 1] > dp[i - 1][j]) {
                    dp[i][j] = arr[i][j] + dp[i - 1][j - 1];

                } else {
                    dp[i][j] = arr[i][j] + dp[i - 1][j];

                }
            }
        }
        // 找到最后一行的最大值
        int max = Integer.MIN_VALUE;
        for (int j = 0; j < n; j++) {
            max = Math.max(max, dp[n - 1][j]);
        }
        return max;
    }

    //自下而上
    static int DataTower_dowToUp() {
        // 数塔问题：给定一个数塔，求从塔顶到塔底的最大路径和
        // 遍历每一列
        for (int j = 0; j < n; j++) {
            // 初始化最后一行的dp值为数塔最后一行的对应值
            dp[n - 1][j] = arr[n - 1][j];
        }

        // 从倒数第二行开始向上遍历每一行
        for (int i = n - 2; i >= 0; i--) {
            // 遍历当前行的每一个元素
            for (int j = 0; j <= i; j++) {
                // 比较当前元素的下一行相邻两个元素的大小
                // 只可能是下一行正下方元素或者正右下方元素
                //path i j 代表第i行j列指向的下一个元素是第几列:j+1/j
                if (dp[i + 1][j] > dp[i + 1][j + 1]) {
                    // 如果左边元素较大，则选择左边路径，并记录路径
                    dp[i][j] = arr[i][j] + dp[i + 1][j];
                    path[i][j] = j;
                } else {
                    // 如果右边元素较大或相等，则选择右边路径，并记录路径
                    dp[i][j] = arr[i][j] + dp[i + 1][j + 1];
                    path[i][j] = j + 1;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(arr[i]));
        }
        System.out.println();
        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println();
        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(path[i]));
        }

        // 输出路径
        System.out.print("路径为：" + arr[0][0]);
        int j = path[0][0]; // 获取第一行的路径索引
        for (int i = 1; i < n; i++) {
            // 从第二行开始，按照记录的路径输出每一行的元素
            System.out.print("-->" + arr[i][j]);
            j = path[i][j]; // 更新路径索引
        }
        System.out.println();
        // 返回塔顶到塔底的最大路径和
        return dp[0][0];
    }


}
